package com.guchenbo.example.ds.heap;

/**
 * Created by CreGu on 2016/5/30.
 */
public class Heap {
    private int[] heapArray;
    private int currentSize;
    private int maxSize;

    public Heap(int maxSize) {
        heapArray = new int[maxSize];
        currentSize = 0;
    }

    public void setUp(int size) {
        for (int i = 0; i < size; i++) {
            insert((int) ((Math.random() * 199) + 1));
        }
    }

    public void insert(int data) {
//        存入数组
        heapArray[currentSize] = data;
//        向上筛选
        trickUp(currentSize);

        currentSize++;
    }

    public void remove() {
//        最末位替换根
        heapArray[0] = heapArray[currentSize - 1];
        currentSize--;

//      向下筛选新根
        trickDown(0);
    }

    public void trickUp(int currIndex) {
        int bottom = heapArray[currIndex];

        int pIndex = (currIndex - 1) / 2;
        while (heapArray[pIndex] < bottom && currIndex > 0) {

            heapArray[currIndex] = heapArray[pIndex];
            currIndex = pIndex;
            pIndex = (currIndex - 1) / 2;
        }
        heapArray[currIndex] = bottom;
    }

    public void trickDown(int currIndex) {
        int top = heapArray[currIndex];

        int leftIndex = currIndex * 2 + 1;
        int rgihtIndex = currIndex * 2 + 2;

        while (leftIndex < currentSize) {

            int largeIndex = leftIndex;
            if (rgihtIndex < currentSize && heapArray[leftIndex] < heapArray[rgihtIndex]) {
                largeIndex = rgihtIndex;
            }

            if (heapArray[largeIndex] > top) {
                heapArray[currIndex] = heapArray[largeIndex];
                currIndex = largeIndex;
            } else {
                break;
            }

            leftIndex = currIndex * 2 + 1;
            rgihtIndex = currIndex * 2 + 2;
        }

        heapArray[currIndex] = top;
    }


    public void display() {
//        print array
        System.out.println("heap array: ");
        for (int i = 0; i < currentSize; i++) {
            System.out.print(heapArray[i] + " ");
        }
        System.out.println();
        String dot = "------------------------";
        System.out.println(dot + dot);
//        print heap
        int nBlanks = 32;//32个空格
        int itemPerRow = 1;//每行几个
        int column = 0;//每行的列
        int index = 0;//数组的第几个

        while (index < currentSize) {
            if (column == 0) {
                for (int j = 0; j < nBlanks; j++)
                    System.out.print(" ");
            }

            System.out.print(heapArray[index++]);

            if (++column == itemPerRow) {
                itemPerRow *= 2;
                nBlanks = (nBlanks / 2);
                column = 0;
                System.out.println();
            } else {
                for (int j = 0; j < nBlanks * 2; j++)
                    System.out.print(" ");
            }
        }
        System.out.println();
    }

}
